LeetCode上一个中等难度的题，可以用递归，当然也可以用动态规划（这道题目的状态转移方程有点复杂，定义为中等让我感觉被鄙视了），下面先上动态规划的代码： class Solution(object): def generateParenthesis(self, n): “”” :type n: int :rtype: List[str] “”” r = [[] for i in range(n+1)] r[0] = [“”] for i in range(1, n+1): for j in range(i): r[i] += [‘(‘+k+’)’+l for k in r[j] for l in r[i-j-1]] return r[n] 推导出dp[n]需要前面所有的状态组合起来： 通俗的说得到n个括号的组合dp[n]就是把一个括号加入到dp[n-1]的每一种组合里且得到的新的括号组合要有效。如何保证加入一个括号后的新组合有效呢？只要被新加入括号括起来的部分k=dp[i]和剩余部分l=dp[n-1-i]都是有效的，换句话说我们要把dp[n-1]中的每一种组合拆分成两部分，并给其中一部分括上一个新括号。 举个例子，如果我们要得到4个括号的组合，那么需要把3个括号所有可能组合的每一种拆分成有效的两部分，拆分完后可能是0+3,1+2,2+1,3+0这四种形式（0代表空字符串，即在dp[3]的左边或右边加一个新的括号，它括住的内容是空）。需要注意的是，并不是dp[3]中的每一种组合都可以拆成这4种，比如((()))这个就只能拆成3+0和0+3。正向思维的拆分看起来是非常复杂的，因为要区别对待各种情况，此时采用反向思维，我们不去拆而是去构建，用来构建的材料则是dp数组中现成的。按照前面的4种拆分形式我们对号入座，做个排列组合就可以了。 每一种拆分形式的两部分dp[i]和dp[n-1-i]做排列组合，并且只给dp[i]部分加括号，可以保证我们得到所有的组合是不重复的。我们称i部分为“括号内”，长度为2i，n-1-i部分为“剩余部分”。我们是给括号内部分整个括上一个括号，长度变成了2i+2，不同的拆分形式之间一定不会重复，因为对i,n-1-i这种拆分，加完括号后，第2i+2和2i+3字符中间一定是可以拆分的，而i+1,n-i以及之后的所有拆分形式在2i+2和2i+3之间是绝不可能有效拆分的。举例来说： ()()() 拆分成 () | ()()和()() | … Continue reading 动态规划：括号生成